/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package org.gephi.statistics.spi;

/**
 *
 * @author lczgywzyy
 */
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Stack;

public class LAF {

    boolean isAF = true;
    LGraph lgraph;
    int n;
    int start, end;
    Stack<Integer> theStack;

//	private ArrayList<Integer> tempList;
    private HashMap<Integer, Integer> tempList;
    private String counterexample;

    private ArrayList<String> resultText = new ArrayList<String>();

    public LAF(LGraph lgraph, int start, int end) {
        this.lgraph = lgraph;
        this.start = start;
        this.end = end;
    }

    @SuppressWarnings("rawtypes")
    public boolean getResult() {
        // lgraph.printGraph();
        n = lgraph.getN();
        theStack = new Stack<Integer>();

        if (!isConnectable(start, end)) {
            isAF = false;
            counterexample = "节点之间没有通路";
        } else {
            // for (int j = 0; j < vertexList.size(); j++) {
            // tempList = new ArrayList<Integer>();
            // for (int i = 0; i < vertexList.size(); i++) {
            // tempList.add(0);
            // }
            // // lgraph.getVertexList()[j].setAllVisitedList(tempList);
            // lgraph.getVertexList().get(j).setAllVisitedList(tempList);
            // }
            Iterator iter = lgraph.getVertexList().entrySet().iterator();
            while (iter.hasNext()) {
                Map.Entry entry = (Map.Entry) iter.next();
                int key = (int) entry.getKey();
                tempList = new HashMap<Integer, Integer>();
                Iterator iter2 = lgraph.getVertexList().entrySet().iterator();
                while (iter2.hasNext()) {
                    Map.Entry entry2 = (Map.Entry) iter2.next();
                    int key2 = (int) entry2.getKey();
                    tempList.put(key2, 0);
                }
//				for (int i = 0; i < lgraph.getVertexList().size(); i++) {
//					tempList.add(0);
//				}
                lgraph.getVertexList().get(key).setAllVisitedList(tempList);
            }

            isAF = af(start, end);
        }
        return isAF;
    }

    @SuppressWarnings("rawtypes")
    private boolean af(int start, int end) {
        lgraph.getVertexList().get(start).setWasVisited(true); // mark it
        theStack.push(start); // push it

        while (!theStack.isEmpty()) {
            int v = getAdjUnvisitedVertex(theStack.peek());
            if (v == -1) // if no such vertex,
            {
                tempList = new HashMap<Integer, Integer>();
//				for (int i = 0; i < lgraph.getVertexList().size(); i++) {
//					tempList.add(0);
//				}
                Iterator iter = lgraph.getVertexList().entrySet().iterator();
                while (iter.hasNext()) {
                    Map.Entry entry = (Map.Entry) iter.next();
                    int key = (int) entry.getKey();
                    tempList.put(key, 0);
                }
                lgraph.getVertexList().get(theStack.peek()).setAllVisitedList(tempList);// 把栈顶节点访问过的节点链表清空
                theStack.pop();
            } else // if it exists,
            {
                theStack.push(v); // push it
            }

            if (!theStack.isEmpty() && end == theStack.peek()) {
                lgraph.getVertexList().get(end).setWasVisited(false); // mark it
                printTheStack(theStack);
                System.out.println();
                theStack.pop();
            }
        }

        return isAF;
    }

    // 判断连个节点是否能连通
    @SuppressWarnings("rawtypes")
    private boolean isConnectable(int start, int end) {
        ArrayList<Integer> queue = new ArrayList<Integer>();
        ArrayList<Integer> visited = new ArrayList<Integer>();
        queue.add(start);
        while (!queue.isEmpty()) {
            // for (int j = 0; j < n; j++) {
            // if (LSparse_Matrix.getInstance().getValue(start, j) == 1 &&
            // !visited.contains(j)) {
            // queue.add(j);
            // }
            // }
            Iterator iter = lgraph.getVertexList().entrySet().iterator();
            while (iter.hasNext()) {
                Map.Entry entry = (Map.Entry) iter.next();
                int key = (int) entry.getKey();
                if (LSparse_Matrix.getInstance().getValue(start, key) == 1 && !visited.contains(key)) {
                    queue.add(key);
                }
            }
            if (queue.contains(end)) {
                return true;
            } else {
                visited.add(queue.get(0));
                queue.remove(0);
                if (!queue.isEmpty()) {
                    start = queue.get(0);
                }
            }
        }
        return false;
    }

    public String counterexample() {
        for (Integer integer : theStack) {
            counterexample += lgraph.displayVertex(integer);
            if (integer != theStack.peek()) {
                counterexample += "-->";
            }
        }

        return counterexample;
    }

    // 与节点v相邻，并且这个节点没有被访问到，并且这个节点不在栈中
    @SuppressWarnings("rawtypes")
    public int getAdjUnvisitedVertex(int v) {
        HashMap<Integer, Integer> arrayList = lgraph.getVertexList().get(v).getAllVisitedList();
//		for (int j = 0; j < n; j++) {
//			if (LSparse_Matrix.getInstance().getValue(v, j) == 1 && arrayList.get(j) == 0 && !theStack.contains(j)) {
//				lgraph.getVertexList().get(v).setVisited(j);
//				return j;
//			}
//		}
        Iterator iter = lgraph.getVertexList().entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            int key = (int) entry.getKey();
            if (LSparse_Matrix.getInstance().getValue(v, key) == 1 && arrayList.get(key) == 0 && !theStack.contains(key)) {
                lgraph.getVertexList().get(v).setVisited(key);
                return key;
            }
        }
        return -1;
    } // end getAdjUnvisitedVertex()

    public void printTheStack(Stack<Integer> theStack2) {
        String tmpString = null;
        for (Integer integer : theStack2) {
            System.out.print(lgraph.displayVertex(integer));
            tmpString += lgraph.displayVertex(integer);
            if (integer != theStack2.peek()) {
                System.out.print("-->");
                tmpString += "-->";
            }
        }
        resultText.add(tmpString);
    }

    public String getResultText() {
        String tmpString = "aaaa\n";
        for (String s : resultText) {
            tmpString += s + "\n";
        }
        return tmpString;
    }

}
